import java.util.ArrayDeque;
import java.util.Queue;

/*
 * @lc app=leetcode.cn id=754 lang=java
 *
 * [754] 到达终点数字
 *
 * https://leetcode-cn.com/problems/reach-a-number/description/
 *
 * algorithms
 * Medium (39.21%)
 * Likes:    91
 * Dislikes: 0
 * Total Accepted:    3.9K
 * Total Submissions: 9.9K
 * Testcase Example:  '1'
 *
 * 在一根无限长的数轴上，你站在0的位置。终点在target的位置。
 *
 * 每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。
 *
 * 返回到达终点需要的最小移动次数。
 *
 * 示例 1:
 *
 *
 * 输入: target = 3
 * 输出: 2
 * 解释:
 * 第一次移动，从 0 到 1 。
 * 第二次移动，从 1 到 3 。
 *
 *
 * 示例 2:
 *
 *
 * 输入: target = 2
 * 输出: 3
 * 解释:
 * 第一次移动，从 0 到 1 。
 * 第二次移动，从 1 到 -1 。
 * 第三次移动，从 -1 到 2 。
 *
 *
 * 注意:
 *
 *
 * target是在[-10^9, 10^9]范围中的非零整数。
 *
 *
 */

// @lc code=start
class Solution {
    public int reachNumber(int target) {
        int n=1;
        Queue<Integer> q = new ArrayDeque<>();
        q.add(0);
        while(!q.isEmpty()){
            for(int i = q.size(); i > 0; i--) {
                int num = q.poll();
                if(num - n == target)
                    return n;
                q.add(num-n);
                if(num + n == target)
                    return n;
                q.add(num+n);
            }
            n++;
        }
        return 0;
    }
}
// @lc code=end

